public class Solution99 {
    TreeNode upper = null;
    TreeNode lower = null;
    TreeNode pre = new TreeNode(Integer.MIN_VALUE);

    public void recoverTree(TreeNode root) {
        helper(root);
        if (upper != null && lower != null) {
            int t = upper.val;
            upper.val = lower.val;
            lower.val = t;
        }
    }

    private void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        helper(root.left);
        if (root.val < pre.val) {
            lower = root;
            if (upper == null) {
                upper = pre;
            }
        }
        pre = root;
        helper(root.right);
    }
}
